Palindromic Partitioning

Statement#

Suppose you are given a string, s. You need to perform the minimum number of cuts to divide the string into substrings, such that all the resulting substrings are palindromes.

Let’s say you have the following string:

• “apple”

The resulting substrings after performing the minimum number of cuts are:

• “a”$|$“pp”$|$“l”$|$“e”

So, a minimum of $3$ cuts are required.

Constraints:

• $1 \leq$ s.length $\leq 600$
• s consists of only lowercase English characters.

Examples#

Try it yourself#

Implement your solution in the following coding playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Palindromic Subsequence dynamic programming pattern.

Naive approach#

A naive approach would be to generate combinations of all possible cuts that can be placed on the string such that all the resulting substrings are palindromes. We will then select the minimum number of cuts.

For example, we have the following string:

s: “abac”

To find the minimum number of cuts, we try all possible combinations:

• “a” |“b” |“a” |“c” — $3$ cuts
• “aba” | “c” — $1$ cut

The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems by placing cuts at every possible position in the string. The position to place a cut is determined using a variable, k, that ranges from, i to j - 1, where i and j are the start and end indexes of the current substring respectively. We store the minimum number of cuts in a variable, result, which is initially set to j, i.e., the maximum number of cuts that can be placed on a string to make the resulting substrings (consisting of one character each) palindromes. This is done based on the following rules:

• Base case: If we have reached the end of the substring, or the current substring is a palindrome, we return $0$.

• Otherwise, we run a loop from k = 0 to k = s.length - 1. On each iteration, we place a cut after the $k^{th}$ index of the string and divide it into two halves. Since we’ve placed one cut, the resulting cost of placing more cuts follows the following recurrence relation, where we now re-evaluate these resulting two halves:

  totalCuts = 1 + min_cuts(s, i, k) + min_cuts(s, k + 1, j)
  

  After an iteration for a value of k is complete, i.e., we have found the total number of cuts that can be placed for a value of k, we take the minimum of the current value of result and totalCuts and store this in result.

• We repeat the above process for all values of k. When the loop ends, result stores the minimum number of cuts, and we return result.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^n)$, where $n$ is the total number of characters in the string.

Space complexity#

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table. In the recursive approach, the following two variables kept changing:

• The start index of the substring, i.
• The end index of the substring, j.

We will use a 2-D table, dp, with i rows and j columns to store the result, i.e., the total number of cuts for the substring, s[i]…s[j].

In addition, we will use a second 2-D table, palindrome_table, with i rows and j columns to store whether the current substring, s[i]…s[j], is a palindrome or not.

At any later time, if we encounter the same sub-problem, we can return the stored result from the table with an $O(1)$ look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in two 2-D tables, the time complexity of this approach is reduced to $O(n^3)$, where $n$ is the number of characters in the string.

Space complexity#

We now need $O(n^2)$ space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems.

We will create a 1-D array, dp, of size $n$. This array will have the following properties:

• Each entry, dp[i], stores the minimum number of cuts required in the substring, s[i]…s[n].

• The array will initially store the value of inf for all of its entries.

We will also create a 2-D table, palindrome_table, of size $(n \times n)$, which stores whether each substring is a palindrome or not. The table will be filled with $1$s and $0$s in the following way:

• If the substring, s[i]…s[j], is a palindrome, palindrome_table[i][j] will be $1$.

• Otherwise, if s[i]…s[j], is not a palindrome, palindrome_table[i][j] will be $0$.

We will traverse the indexes, i, of s from right to left and fill the dp array in the following manner:

• If palindrome_table[i][n - 1] is $1$, this means s[i]…s[n - 1] is a palindrome, so we fill dp[i] with $0$ since no cuts are required.

  if palindrome_table[i][n - 1] == 1:
     dp[i] = 0
  

• Otherwise, we will look for a palindrome in the remaining substring s[i]…s[n - 2]. We traverse the indexes, j, of this substring from right to left in the following manner:

  • We check whether palindrome_table[i][j] is $1$. If it is, s[j]…s[n - 1] is a palindrome. So we update dp[i] with the minimum of its current value and 1 + dp[j + 1]:

    if palindrome_table[i][j] == 1:
       dp[i] = min(dp[i], 1 + dp[j + 1])
    

After the outer loop has ended, dp[0] will contain the minimum cuts required on the entire string, so we return dp[0].

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D table to store the results of subproblems that would be used later on, therefore, the time complexity of this approach will also be $O(n^2)$.

Space complexity#

We need $O(n^2)$ space in memory to store the intermediate values.